Información del Plan Docente

1. Información básica de la asignatura

En esta asignatura el alumno mejorará su capacidad para diseñar y desarrollar algoritmos incidiendo en las técnicas probabilistas, aproximadas y heurísticas. El alumno aprenderá a reconocer los problemas en cuya solución se utilizan esas técnicas, a diseñar algoritmos que las utilicen y a justificar la corrección y eficiencia de los mismos.

2. Resultados de aprendizaje

El estudiante, para superar esta asignatura, deberá demostrar los siguientes resultados...

1. Conoce los modelos de computación no exactos y es capaz de seleccionar el adecuado y utilizarlo para el modelado de dominios de aplicación heterogéneos.
2. Es capaz de identificar los problemas NP-difíciles.
3. Conoce técnicas algorítmicas probabilistas, aproximadas y heurísticas para los mismos.
4. Sabe identificar las componentes más relevantes de un problema y seleccionar la técnica aproximada más adecuada para el mismo, además de argumentar de forma razonada dicha elección.
5. Sabe comparar problemas y utilizar dicha comparación para resolver un problema a partir de una solución eficiente de otro.
6. Sabe razonar sobre la tasa de error y la eficiencia de los algoritmos aproximados y probabilistas.
7. Sabe aplicar el análisis amortizado de eficiencia a estructuras de datos avanzadas.
8. Puede trabajar en grupo, identificar objetivos del grupo, trazar un plan de trabajo para alcanzarlo, reconocer los diferentes papeles dentro de un equipo y asume el compromiso de las tareas encomendadas.
9. Gestiona el auto-aprendizaje y el desarrollo incluyendo el tiempo de gestión y de organización.
10. Aprecia la necesidad del aprendizaje continuo.

3. Programa de la asignatura

1. Introducción. Los problemas NP-difíciles. Los problemas de optimización.
2. Algoritmos aproximados. Concepto. Diseño de algoritmos. Garantías y límites.
3. Algoritmos probabilistas: Las Vegas y Montecarlo. Análisis. Generadores pseudoaleatorios.
4. Heurísticas. Simulated annealing (templado simulado).
5. Algoritmos genéticos.
6. Análisis amortizado. Estructuras de datos avanzadas.
7. Algoritmos especializados.

4. Actividades académicas

El programa que se ofrece al estudiante para ayudarle a lograr los resultados previstos comprende las siguientes actividades...

1. En las clases impartidas en el aula se desarrollará el temario de la asignatura.
2. En las clases de problemas se resolverán problemas de aplicación de los conceptos y técnicas presentadas en el programa de la asignatura. Se propondrán problemas y ejercicios para ser resueltos antes de la clase de problemas en la que se presentarán y discutirán diferentes soluciones a dichos problemas. También se propondrán ejercicios durante la sesión de problemas para ser resueltos durante la misma, algunos de forma individual y otros para ser trabajados en grupo.
3. El trabajo de prácticas se desarrolla en un laboratorio informático o bien en los computadores personales de los alumnos. En estas sesiones los alumnos deberán trabajar en equipo y realizar una serie de trabajos de programación directamente relacionados con los temas estudiados en la asignatura. Para ello se propondrán una serie de trabajos o ejercicios de programación para que los alumnos los resuelvan en grupo y los entreguen dentro de los plazos de tiempo que se fijen en cada caso.

5. Sistema de evaluación

El estudiante deberá demostrar que ha alcanzado los resultados de aprendizaje previstos mediante las siguientes actividades de evaluación

Opción recomendada (liberación progresiva de exámenes finales):

1. Parte práctica:
   • Prácticas de laboratorio (en grupo) durante el cuatrimestre: 20%.
2. Parte de teoría y problemas:
   • Ejercicios de trabajo individual durante el cuatrimestre: 20%.
   • Prueba escrita intermedia: 30%.
   • Examen final (realizar sólo una parte): 30%.

Opción basada exclusivamente en exámenes finales:

1. Parte práctica:
   • Examen práctico (individual) de programación: 20%.
2. Parte de teoría y problemas:
   • Examen final (realizarlo completo): 80%.